import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 25397
 * Date: 2022-01-16
 * Time: 17:49
 */
public class MyStack {
    //用队列实现栈
    private Queue<Integer> queue1;
    private Queue<Integer> queue2;

    public MyStack(){
        queue1=new LinkedList<>();
        queue2=new LinkedList<>();
    }

    public void push(int x){//入栈
        if (!queue1.isEmpty()){
            queue1.offer(x);
        }else if(!queue2.isEmpty()){
            queue2.offer(x);
        }else{//两个都为空，我们默认放到queue1里面
            queue1.offer(x);
        }
    }

    public int pop(){//出栈
        if(empty()){//两队列全为空的情况——也就是栈里没有元素了
            return -1;
        }
        if (!queue1.isEmpty()){
            int size=queue1.size();//这里不能直接把queue1.size()放到for循环里面
            //因为你for循环里面每次都要出一个元素，size会越来越小
            //比如原先size=4，里面4个元素，i=0
            //出一个元素，size=3，里面3个元素,i=1
            //出一个元素，size=2，里面2个元素,i=2
            //这时显然我们需要的循环还没有结束，但是如果直接把queue1.size()放到for循环里面它已经结束了
            for(int i=0;i<size-1;i++){
                    //把queue1里面的元素出到queue2里面
                    //一共出size-1个——queue1最后一个也就是我们要pop的元素
                    int val=queue1.poll();
                    queue2.offer(val);
                }
                return queue1.poll();
            }
        if (!queue2.isEmpty()){
            int size=queue2.size();
            for(int i=0;i<size-1;i++){
                    //把queue2里面的元素出到queue1里面
                    //一共出size-1个——queue2最后一个也就是我们要pop的元素
                    int val=queue2.poll();
                    queue1.offer(val);
                }
                return queue2.poll();
            }
        return -1;//这里是为了编译不报错，因为上面都是用的if，这句代码实际用不到，仅仅是为了编译通过

    }

    public int top(){//得到队头元素
        if(empty()){
            return -1;
        }

        if(!queue1.isEmpty()){
            int val=0;
            int size=queue1.size();
            for (int i=0;i<size;i++){
                val=queue1.poll();
                queue2.offer(val);
            }
            return val;
        }

        if ((!queue2.isEmpty())){
            int val=0;
            int size=queue2.size();
            for(int i=0;i<size;i++){
                val=queue2.poll();
                queue1.offer(val);
            }
            return val;
        }
        return -1;
    }

    public boolean empty(){//判断栈是否为空
        return queue1.isEmpty()&&queue2.isEmpty();
    }

    /*public static void main(String[] args) {
        MyStack myStack=new MyStack();
        //入栈
        myStack.push(1);
        myStack.push(2);
        myStack.push(3);
        myStack.push(4);
        System.out.println(myStack.top());//打印栈顶元素4

        //出栈
        myStack.pop();//删除栈顶元素4
        System.out.println(myStack.top());//打印栈顶元素3
    }*/


    //力扣150，逆波兰求值
    /*public int evalRPN(String[] tokens) {
        Stack<Integer> stack=new Stack<>();

        for(int i=0;i<tokens.length;i++){
            String val=tokens[i];
            if(!isOperation(val)){
                //不是运算符（是运算数据）
                stack.push(Integer.parseInt(val));
                //这里不能直接放，因为我们直接放的话是字符串，但栈里存放的是整形
            }else{
                //是运算符
                //判断是什么运算符
                int num2=stack.pop();
                int num1=stack.pop();
                switch(val){
                    case "+":
                        stack.push(num1+num2);
                        break;
                    case "-":
                        stack.push(num1-num2);
                        break;
                    case "*":
                        stack.push(num1*num2);
                        break;
                    case "/":
                        stack.push(num1/num2);
                        break;
                }
            }
        }
        return stack.pop();
    }
    private boolean isOperation(String x){
        if(x.equals("+")||x.equals("-")||x.equals("*")||x.equals("/")){
            return true;
        }else{
            return false;
        }
    }*/

    public int calPoints(String[] ops) {
        return evalRPN(ops);
    }
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack=new Stack<>();
        for(int i=0;i<tokens.length;i++){
            String val=tokens[i];
            if(!isOperation(val)){
                //不是运算符（是运算数据）
                stack.push(Integer.parseInt(val));
                //这里不能直接放，因为我们直接放的话是字符串，但栈里存放的是整形
            }else{
                //是运算符
                //判断是什么运算符
                if(val.equals("+")){
                    int num2=stack.pop();
                    int num1=num2+stack.peek();
                    stack.push(num2);
                    stack.push(num1);
                }else if(val.equals("C")){
                    stack.pop();
                }else if(val.equals("D")){
                    int num3=stack.pop();
                    stack.push(num3);
                    stack.push(2*num3);
                }
            }
        }
        return stack.pop();
    }
    private boolean isOperation(String x){
        if(x.equals("+")||x.equals("C")||x.equals("D")){
            return true;
        }else{
            return false;
        }
    }

    public static void main(String[] args) {
        MyStack myStack=new MyStack();
        String[]ops={"5","2","C","D","+"};
        myStack.calPoints(ops);
    }
}
